Chapter 7. Quantum Error Correction Codes (QECC)
In Chapter 6, we learned that real qubits are exposed to discrete errors such as \(X\) (bit-flip), \(Z\) (phase-flip), and \(Y\) (both). If these errors cannot be corrected, a quantum computer would lose all information to random noise after just a few gates due to errors.
But how can quantum information be “corrected”? Classical computers replicate ‘1’ as ‘111’ and later detect errors via majority voting. However, quantum mechanics prohibits copying an arbitrary qubit state \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\) due to the No-Cloning Theorem.
Quantum Error Correction Codes (QECC) is a remarkable technique that disperses (encodes) information across multiple qubits without “copying” or “direct measurement” (which collapses superposition), and identifies only the “symptoms” of errors using ancilla qubits.
1. Fundamental Concepts
No-Cloning Theorem: There is no unitary operator that can copy an arbitrary unknown quantum state \(|\psi\rangle\) into \(|\psi\rangle|\psi\rangle\). This violates the linearity of quantum mechanics.
Detailed Explanation: If a cloning operator \(U\) exists, \(U|\psi_A\rangle|0\rangle = |\psi_A\rangle|\psi_A\rangle\) and \(U|\psi_B\rangle|0\rangle = |\psi_B\rangle|\psi_B\rangle\) must hold. By linearity, \(U(\alpha|\psi_A\rangle + \beta|\psi_B\rangle)|0\rangle = \alpha|\psi_A\rangle|\psi_A\rangle + \beta|\psi_B\rangle|\psi_B\rangle\). However, the state we want to copy is \((\alpha|\psi_A\rangle + \beta|\psi_B\rangle)\), so the result of the copy should be \((\alpha|\psi_A\rangle + \beta|\psi_B\rangle) \otimes (\alpha|\psi_A\rangle + \beta|\psi_B\rangle)\). These two results are obviously different due to the cross terms in \(\alpha\beta\).
Three Steps of Error Correction:
- Encoding: Disperse and entangle 1 logical qubit (\(|\psi\rangle_L\)) information across \(n\) physical qubits.
- Syndrome Measurement: Extract information (syndrome) about whether an error occurred, what type of error it is, and where it occurred, without disturbing the original data, using ancilla qubits.
- Recovery: Apply recovery operations (e.g., \(X_3\)) corresponding to the measured syndrome to reverse the error.
Syndrome - Symptoms of Errors: The key idea is to obtain only error information without querying the state of the data (\(\alpha, \beta\)).
- Example: In a 3-qubit code, we do not ask whether the first qubit is \(|0\rangle\) or \(|1\rangle\).
- Instead, we ask whether the first and second qubits are the same or different compared to the expected error-free state.
- This “same/different” information is the syndrome, and it does not collapse the superposition of \(\alpha, \beta\).
Code Space: It is a 2-dimensional subspace of the \(n\)-qubit Hilbert space where the encoded ‘logical 0’ and ‘logical 1’ reside.
- \(|0\rangle_L = \text{encoded 0 state}\)
- \(|1\rangle_L = \text{encoded 1 state}\)
- General logical state: \(|\psi\rangle_L = \alpha|0\rangle_L + \beta|1\rangle_L\)
2. Symbols and Key Relations
Logical States: \(|\psi\rangle_L = \alpha|0\rangle_L + \beta|1\rangle_L\)
Error Operators: Kraus operators \(\{K_i\}\) from Chapter 5 of “Quantum History” (here denoted as \(X_1, Z_3\), etc.)
Syndrome Operators: It is a set of Hermitian operators (observables) \(\{M_k\}\) used to detect errors. (Examples: \(Z_1 Z_2\), \(Z_2 Z_3\))
- Condition for error-free states: All states \(|\psi\rangle_L\) in the code space must be common eigenstates of all \(M_k\) (typically with eigenvalue +1). \(M_k |\psi\rangle_L = (+1) |\psi\rangle_L\).
Error Detection: If an error \(E\) occurs, the state becomes \(|\psi'\rangle = E |\psi\rangle_L\). When \(M_k\) and \(E\) anticommute (\(M_k E = -E M_k\)), the syndrome changes. \(M_k |\psi'\rangle = M_k E |\psi\rangle_L = -E M_k |\psi\rangle_L = -E |\psi\rangle_L = -|\psi'\rangle\).
- The measured eigenvalue changes from \(+1\) to \(-1\), indicating that an error \(E\) has occurred.
Recovery: When a syndrome \(s\) is measured, the corresponding recovery operation \(R_s\) is applied to restore \(R_s E |\psi\rangle_L \propto |\psi\rangle_L\).
3. Examples with Deeper Insight
Example 1: 3-Qubit Bit Flip Code (\(X\) Error Correction)
- Objective: Detects and corrects 1-qubit \(X\) errors (e.g., \(X_1, X_2, X_3\)).
- Encoding: (Similar to classical repetition but with superposition possible)
- \(|0\rangle_L = |000\rangle\)
- \(|1\rangle_L = |111\rangle\)
- Logical state: \(|\psi\rangle_L = \alpha|000\rangle + \beta|111\rangle\)
- \(|0\rangle_L = |000\rangle\)
- Syndrome Operators: “Are neighbors the same?”
- \(M_1 = Z_1 Z_2\) (Z-parity of qubits 1-2)
- \(M_2 = Z_2 Z_3\) (Z-parity of qubits 2-3)
- \(M_1 = Z_1 Z_2\) (Z-parity of qubits 1-2)
- Syndrome Measurement (Operation Principle):
- No error (\(I\)): Applying \(M_1\) to \(|\psi\rangle_L\) gives \(Z_1 Z_2 |000\rangle = (+1)|000\rangle\) and \(Z_1 Z_2 |111\rangle = (+1)|111\rangle\), so the eigenvalue is always \(+1\). \(M_2\) also gives \(+1\).
- Syndrome: (+1, +1) \(\equiv\) (0, 0)
- Syndrome: (+1, +1) \(\equiv\) (0, 0)
- \(X_1\) error (\(X_1 \otimes I \otimes I\)):
- \(|\psi'\rangle = X_1 |\psi\rangle_L = \alpha|100\rangle + \beta|011\rangle\)
- \(M_1\) measurement: \(Z_1 Z_2 |100\rangle = (-1)|100\rangle\), \(Z_1 Z_2 |011\rangle = (-1)|011\rangle\). Eigenvalue \(-1\).
- \(M_2\) measurement: \(Z_2 Z_3 |100\rangle = (+1)|100\rangle\), \(Z_2 Z_3 |011\rangle = (+1)|011\rangle\). Eigenvalue \(+1\).
- Syndrome: (-1, +1) \(\equiv\) (1, 0)
- \(|\psi'\rangle = X_1 |\psi\rangle_L = \alpha|100\rangle + \beta|011\rangle\)
- \(X_2\) error:
- \(M_1\) measurement: Eigenvalue \(-1\).
- \(M_2\) measurement: Eigenvalue \(-1\).
- Syndrome: (-1, -1) \(\equiv\) (1, 1)
- \(M_1\) measurement: Eigenvalue \(-1\).
- No error (\(I\)): Applying \(M_1\) to \(|\psi\rangle_L\) gives \(Z_1 Z_2 |000\rangle = (+1)|000\rangle\) and \(Z_1 Z_2 |111\rangle = (+1)|111\rangle\), so the eigenvalue is always \(+1\). \(M_2\) also gives \(+1\).
- Recovery:
| Syndrome | Measured eigenvalue (\(M_1, M_2\)) | Detected error | Recovery operation |
| :— | :— | :— | :— |
| (0, 0) | (+1, +1) | No error | \(I\) (do nothing) |
| (1, 0) | (-1, +1) | \(X_1\) error | Apply \(X_1\) |
| (1, 1) | (-1, -1) | \(X_2\) error | Apply \(X_2\) |
| (0, 1) | (+1, -1) | \(X_3\) error | Apply \(X_3\) |
- 💡 Detailed Explanation (Why information is not collapsed)
> When measuring the syndrome \(M_1 = Z_1 Z_2\), we obtain only a single piece of information: “the eigenvalue is \(-1\)” for the entire state \(\alpha|100\rangle + \beta|011\rangle\).
> This measurement does not collapse \(|\psi'\rangle\) into \(\alpha|100\rangle\) or \(\beta|011\rangle\). This is because both terms (\(|100\rangle, |011\rangle\)) have the same eigenvalue \(-1\) for \(M_1\), so their superposition is preserved after the measurement.
> In other words, we have successfully extracted information about the error (\(X_1\)) while keeping the information about \(\alpha, \beta\) (the information we want to preserve) hidden.
- Encoding: (Similar to classical repetition but with superposition possible)
Example 2: 3-qubit phase-flip code (\(Z\) error correction)
- Goal: Corrects a 1-qubit \(Z\) error.
- Core Trick: Uses the \(HXH=Z\) relation from Chapter 2 of “Quantum Mechanics.” A \(Z\) error is equivalent to an \(X\) error in the Hadamard (\(H\)) basis.
- Encoding: Apply \(H\) to all qubits of the bit-flip code.
- \(|0\rangle_L = H^{\otimes 3}|000\rangle = |+++\rangle = \frac{1}{\sqrt{8}}(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)\)
- \(|1\rangle_L = H^{\otimes 3}|111\rangle = |---\rangle = \frac{1}{\sqrt{8}}(|0\rangle-|1\rangle)(|0\rangle-|1\rangle)(|0\rangle-|1\rangle)\)
- \(|0\rangle_L = H^{\otimes 3}|000\rangle = |+++\rangle = \frac{1}{\sqrt{8}}(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)\)
- Error (\(Z_1\)): If a \(Z_1\) error occurs, \(|\psi\rangle_L = \alpha|+++\rangle + \beta|---\rangle\) becomes
\(|\psi'\rangle = Z_1(\alpha|+++\rangle + \beta|---\rangle) = \alpha(Z_1|{+}\rangle)|++\rangle + \beta(Z_1|{-}\rangle)|--\rangle\)
Since \(Z_1|{+}\rangle = |{-}\rangle\) and \(Z_1|{-}\rangle = |{+}\rangle\),
\(|\psi'\rangle = \alpha|-++\rangle + \beta|+--\rangle\). (Same form as the \(X_1\) error in the bit-flip code)
- Syndrome Operator: Just as \(Z_i Z_j\) is used to detect \(X\) errors, \(X_i X_j\) is used to detect \(Z\) errors.
- \(M_1 = X_1 X_2\)
- \(M_2 = X_2 X_3\)
- \(M_1 = X_1 X_2\)
- Recovery: Use the same syndrome table as for \(X\) errors, but apply \(Z_k\) instead of \(X_k\) for the recovery operation.
- Core Trick: Uses the \(HXH=Z\) relation from Chapter 2 of “Quantum Mechanics.” A \(Z\) error is equivalent to an \(X\) error in the Hadamard (\(H\)) basis.
Example 3: 9-qubit Shor code (Corrects all single-qubit errors)
- Objective: Corrects any error in \(X, Z, Y\) that occurs in one of the 9 qubits.
- Encoding (Combination of Two Codes):
- Phase Protection (Outer Code): First, encode 1 qubit into a 3-qubit phase flip code. \(|\psi\rangle = \alpha|0\rangle + \beta|1\rangle \to |\psi_{step1}\rangle = \alpha|+++\rangle + \beta|--- \rangle\)
- Bit Protection (Inner Code): Re-encode each of the above 3 qubits individually into a 3-qubit bit flip code. (Total \(3 \times 3 = 9\) qubits) \(|+\rangle \to |+\rangle_L = \frac{1}{\sqrt{2}}(|000\rangle + |111\rangle)\) \(|-\rangle \to |-\rangle_L = \frac{1}{\sqrt{2}}(|000\rangle - |111\rangle)\)
- Final State (Very Complicated 9-Qubit Entangled State): \(|0\rangle_L = \frac{1}{\sqrt{8}}(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)\) \(|1\rangle_L = \frac{1}{\sqrt{8}}(|000\rangle-|111\rangle)(|000\rangle-|111\rangle)(|000\rangle-|111\rangle)\)
- Syndrome Measurement:
- Measure bit flip syndrome of type \(Z_i Z_{i+1}\) within each block of 3 qubits (1-3, 4-6, 7-9). (Total of 6 measurements)
- Measure phase flip syndrome of type \(X_i X_j\) between the 3 blocks. (Total of 2 measurements)
- With a total of 8 syndrome measurements, you can precisely identify where an \(X\) or \(Z\) error occurred among the 9 qubits.
- 💡 Detailed Explanation (What about Y errors?): > In Chapter 6 of “Quantum History”, we learned that \(Y = iXZ\). If a \(Y_1\) error occurs, this is equivalent to an \(X_1\) error and a \(Z_1\) error occurring simultaneously on the first qubit. > The Shor code detects the \(X_1\) error via bit flip syndrome and detects the \(Z_1\) error via phase flip syndrome. If both syndromes point to the first qubit, we apply the recovery operation \(Y_1 = iXZ\) (or simply \(XZ\)) to correct both errors at once. (The global phase \(i\) can be ignored) > This allows us to correct all single-qubit errors.
- Encoding (Combination of Two Codes):
4. Practice Problems
- Syndrome Calculation: In the 3-qubit bit flip code, when an \(X_3\) error occurs on the third qubit, calculate the eigenvalues of \(M_1 = Z_1 Z_2\) and \(M_2 = Z_2 Z_3\).
- Circuit Drawing: Draw the quantum circuit for measuring the syndrome \(M_1 = Z_1 Z_2\) in the 3-qubit bit flip code using 2 CNOT gates and 1 ancilla qubit. (Hint: Use the ancilla qubit as the control)
- Error Cross-talk: Assume the 3-qubit bit flip code (\(|000\rangle, |111\rangle\)) experiences a \(Z_1\) phase flip error instead of an \(X\) error. Can the syndrome operators (\(M_1, M_2\)) detect this error? Why or why not?
- Shor Code Capacity: The 9-qubit Shor code uses \(n=9\) physical qubits to protect \(k=1\) logical qubit. When this code can correct \(t=1\) single-qubit errors, what is the \((n, k, d)\) parameter (where \(d=2t+1\)) called? (Common sense question)
5. Explanation
- \(|\psi'\rangle = X_3 |\psi\rangle_L = \alpha|001\rangle + \beta|110\rangle\).
- \(M_1 = Z_1 Z_2\): \(Z_1 Z_2 |001\rangle = (+1)|001\rangle\), \(Z_1 Z_2 |110\rangle = (+1)|110\rangle\). eigenvalue +1.
- \(M_2 = Z_2 Z_3\): \(Z_2 Z_3 |001\rangle = (-1)|001\rangle\), \(Z_2 Z_3 |110\rangle = (-1)|110\rangle\). eigenvalue -1.
- Syndrome: (+1, -1) \(\equiv\) (0, 1). (Matches the table in Example 1)
- Prepare the ancilla qubit as \(|0\rangle_a\) and apply the H gate \(\to |+\rangle_a\). \(|0\rangle_a \to [H] \to \bullet (\text{control}) \to \bullet (\text{control}) \to [H] \to \text{measurement}\) \(\quad \quad \quad \quad \quad | \quad \quad \quad \quad |\) \(|q_1\rangle \to \quad \quad \oplus (\text{target}) \quad \quad\) \(|q_2\rangle \to \quad \quad \quad \quad \quad \oplus (\text{target})\) (Revised) Measuring the \(Z\) operator has the opposite direction of CNOT. \(|0\rangle_a \to [H] \to \text{CNOT(control:q1, target:a)} \to \text{CNOT(control:q2, target:a)} \to [H] \to \text{measurement}\) (Revised again) Measuring \(Z_1 Z_2\) is simpler. \(|0\rangle_a \to \text{CNOT(control:q1, target:a)} \to \text{CNOT(control:q2, target:a)} \to \text{measurement}\) (No H gate) Prepare the ancilla qubit as \(|0\rangle\). CNOT(1→a) \(\to\) CNOT(2→a) \(\to\) measure the ancilla qubit. If the measurement result is ‘1’, it means eigenvalue -1; if ‘0’, it means +1.
- \(|\psi'\rangle = Z_1 |\psi\rangle_L = Z_1(\alpha|000\rangle + \beta|111\rangle) = \alpha|000\rangle - \beta|111\rangle\).
- \(M_1 = Z_1 Z_2\): \(Z_1 Z_2(\alpha|000\rangle - \beta|111\rangle) = \alpha(+1)|000\rangle - \beta(+1)|111\rangle = +1 |\psi'\rangle\).
- \(M_2 = Z_2 Z_3\): \(Z_2 Z_3(\alpha|000\rangle - \beta|111\rangle) = \alpha(+1)|000\rangle - \beta(+1)|111\rangle = +1 |\psi'\rangle\).
- The syndrome is (0, 0). \(Z\) error is not detected. The bit-flip code is specialized only for \(X\) errors and is completely vulnerable to \(Z\) errors.
- \(n=9\) (number of physical qubits), \(k=1\) (number of logical qubits), \(t=1\) (number of correctable errors). The ‘distance’ \(d\) of an error code is defined as \(d=2t+1\). Since \(t=1\), \(d=3\). It is denoted as \([[n, k, d]]\) code, and the Shor code is [[9, 1, 3]] code.